home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 275_01 / lcau.tex < prev    next >
Text File  |  1980-01-01  |  23KB  |  507 lines
  1.  
  2. \documentstyle{article}
  3. \topmargin 0in \textheight 434pt
  4. \evensidemargin 0.5in \oddsidemargin 0.5in
  5. \textwidth 360pt \marginparwidth 0in \marginparsep 0pt
  6.  
  7. \begin{document}
  8. \title{LCAU.DOC}
  9.  
  10. \author{
  11. Harold V. McIntosh \\
  12. Departamento de Aplicaci\'on de Microcomputadoras,\\
  13. Instituto de Ciencias, Universidad Aut\'onoma de Puebla,\\
  14. Apartado postal 461, 72000 Puebla, Puebla, M\'exico.}
  15.  
  16. \date{\today}
  17. \maketitle 
  18.  
  19. \begin{abstract} 
  20. A previous collection of celular automata programs has been extended in 
  21. three directions; also certain minor errors have been corrected. 
  22. \begin{enumerate} 
  23. \item General rules, not just totalistic rules, may be analyzed.
  24. \item Cell densities and block probabilities may be calculated 
  25. according to mean field theory and local structure theory using options 
  26. in a new submenu.
  27. \item An option to produce de~Bruijn diagrams is incorporated in another 
  28. new submenu. 
  29. \end{enumerate} 
  30. Consequently a more detailed and convenient analysis of $(k,1), k=2,3,4$ 
  31. and $(2,2)$ automata may be made than previously.  
  32. \end{abstract}
  33.  
  34. The disk LCAU.C supplements the disk LCA.C which was released in the 
  35. summer of 1987. Both source code and a separate disk of .EXE files are 
  36. provided. The original disk contained 9 programs written in ``C'' to 
  37. calculate and display the evolution of linear cellular automata. 
  38. Although the programs represented a point in the evolution of the 
  39. course {\em Fortran III} offered during the past several semesters, at 
  40. the {\em Universidad Aut\'onoma de Puebla}, and were promoted at the 
  41. {\em XVI Feria de Puebla}, they had their principal inspiration in an 
  42. article in the December, 1986, issue of Byte magazine which explained 
  43. how cellular automata could lead to intricate and complicated designs, 
  44. with a certain aesthetic appeal. 
  45.  
  46. \begin{quotation} 
  47. \noindent
  48.     Kenneth E. Perry, \\
  49.     Abstract mathematical art, \\
  50.     Byte, December 1986, pages 181-192. 
  51. \end{quotation} 
  52.  
  53. The 9 programs in the LCAkr.C set ran through the $k$-range of 2, 3, 
  54. and 4 states per cell, as well as interactions between first, second, 
  55. or third neighbors (the $r$-range). The combinations (4,1) and (4,2) 
  56. are surely the most colorful, but the binary first neighbor version 
  57. (2,1) is more amenable to an exhaustive analysis.
  58.  
  59. Programs in the new series are named LCAU to distinguish them from 
  60. members of the old series. 
  61.  
  62. In the old series, In all cases except for (2,1), only totalistic rules 
  63. were considered. Totalistic rules are those for which the transition 
  64. depends only on the number of cells of different kinds in each 
  65. neighborhood, but not on their precise arrangement. More exactly, each 
  66. state gets assigned an integer in the range 0 to $k-1$ as a weight, the 
  67. actual transition being a function of the weighted sum of all the 
  68. neighbors (including the evolving cell). The artistic effects arise 
  69. from assigning colors to each of cell values. 
  70.  
  71. Although the use of totalistic rules serves to reduce the enormous 
  72. number of possible automata greatly, it excludes many interesting 
  73. possiblilities arising from a more detailed specification of the 
  74. evolutionary rules. When k, the number of states per cell is small, 
  75. there is not too much which is possible in the way of design, but once 
  76. it reaches 4 or beyond some interesting constructions become possible. 
  77. LCA41.C in particular, contains enhanced rule and line editing menus 
  78. which allow experimentation with the design of rules.
  79.  
  80. Certain of the demonstrations in LCAU41.C show how the design process 
  81. can be used. There is an example of a ``binary counter'' which consists 
  82. of a glider gun together with bistable targets. In one state the target 
  83. absorbs the glider and changes to the other state. In the second state 
  84. the target passes the glider, reverting to the first state. Thus half 
  85. the gliders are lost to each target, whose state forms a binary counter 
  86. whose carry is represented by the gliders which are allowed to pass. 
  87.  
  88. Another demonstration shows how a bouncing glider may shuttle between 
  89. two obstacles - still lifes - drawing them ever closer together. Just 
  90. as the glider is about to be crushed, the walls coalesce but the glider 
  91. escapes to one side, seeking new walls to conquer. Multiple gliders may 
  92. go about their business, competing for the wall if they lie on opposite 
  93. sides or hastening the squeeze if they lie on the same side.
  94.  
  95. A third demonstration shows a slow glider propelled by an internal 
  96. glider or gliders bouncing back and forth - a sort of Mexican jumping 
  97. bean. When a fast glider overtakes a slower glider, they coalesce, 
  98. producing an even slower glider. 
  99.  
  100. A fourth demonstration shows gliders of two different velocities, which
  101. can be used to set up a remote still life whose reaction to further 
  102. gliders gives it a life of its own. 
  103.  
  104. Such constructions can be used to generate interesting patterns, but 
  105. they also serve theoretical ends as well. For example, the binary 
  106. counters establish the existence of structures with both exponentially 
  107. long transients and exponentially long cycles. Since they still use 
  108. several cells to establish the basic components and their spacings, 
  109. they still do not reach theoretical maxima; but they do lie within 
  110. certain factors of such maxima.
  111.  
  112. When $k$ becomes larger still, universal Turing machines can be 
  113. programmed, but this probably requires a $k$ of at least 6 or 8.
  114.  
  115. Another extensive addition which has been made to the programs is to be 
  116. found in the series PROB.C, which can be invoked by typing $t$ in the 
  117. main menu (the old totalistic rule number can still be utilized by 
  118. typing $T$); in fact their inclusion more than doubles the size of the 
  119. programs. These new programs permit a statistical survey of the 
  120. properties of the automaton. Originally they calculated simple 
  121. probabilities on the basis of ideas which go by the name of ``mean field 
  122. theory,'' whose results were plausible but not entirely convincing.
  123.  
  124. Since then two interesting articles have appeared 
  125.  
  126. \begin{quote} 
  127. \noindent
  128.     W. John Wilbur, David J. Lipman and Shihab A. Shamma, \\
  129.     On the     prediction of local patterns in cellular automata, \\
  130.     Physica {\bf 19D} 397-410 (1986).
  131.  
  132. \noindent
  133.     Howard A. Gutowitz, Jonathan D. Victor and Bruce W. Knight, \\
  134.     Local structure theory for cellular automata, \\
  135.     Physica {\bf 28D} 18-48 (1987). 
  136. \end{quote} 
  137.  
  138. These articles, from differing points of view, show how to take 
  139. correlations between cells into account by calculating the 
  140. probabilities of strings of cells. Rather than taking individual 
  141. probabilties as fundamental and deducing the probabilities of 
  142. combinations, the process is inverted; self consistent probabilities 
  143. for strings (or blocks) of a certain length are found from which the 
  144. probabilities of individual cells are obtained by averaging.
  145.  
  146. The calculations of these articles have been included among the options 
  147. of the $t$ submenu, so that probabilities derived from blocks of length 
  148. up to 6 can be compared with simpler estimates and with the actual 
  149. performance of the automaton.
  150.  
  151. A third feature of the new series is the incorporation of the de Bruijn 
  152. diagrams within the main program, together with a visual representation 
  153. in terms of chords of a circle. It is still not possible to transfer 
  154. the cycles obtained back to the main program without copying them on 
  155. paper and editing the initial line with the option $l$. Limitations of 
  156. space and time severely restrict the lengths of periods which can be 
  157. analyzed. Although interesting gliders and cycles are found within the 
  158. accessible range of the program, there are many others of longer 
  159. periods which manifest themselves experimentally when the evolutions 
  160. are run. It would be nice if the exhaustive analysis afforded by the 
  161. de Bruijn diagrams were feasible for the longer periods that show up on 
  162. the screen, but they would really require a faster computer, more 
  163. memory, and probably programs incorporating finer details of the 
  164. algorithms used. 
  165.  
  166. The programs contain a bare minimum of help facilities, in the sense